Geographic data can be represented as points, polygons and polygonal paths. When processing such data it is often required to execute queries e.g. “Do these polygons intersect?” or construct new data e.g. the intersection of two polygons. For efficient execution of queries in databases (e.g. “Select all the entries that intersect this polygon”), a spatial index, for example, that is based on a rectangular grid can be employed to avoid fetching entries that are irrelevant. For processing round earth data, it is highly desirable to fit the entire globe with a rectangular grid in a way that minimizes distortions.
Geographic data come in two flavors: planar coordinates in a specific map, and latitude-longitude coordinates on a round earth. The algorithms for queries and constructions are very elaborate and complex. It is therefore highly desirable to utilize the same implementation of algorithms for planar and round earth computations. Typically, geographic data is projected onto a plane and then processed. The projection can be edge-preserving, such that, it can map round-earth polygon edges to linear segments in the plane. Non-numerical planar geometric algorithms can be applied to (round earth) geographical objects after they have been projected to a plane. The type of projection can vary, depending on the type of operation and the extents of the operands.
Unfortunately, a single projection cannot map the entire globe to a plane. Moreover, the extents of the scene that may be mapped to a plane with any single projection are limited by distortion at the fringes. Conventional systems partition a scene into a plurality of patches to minimize distortion, and project each patch to a different plane. The computation can be performed piecemeal in each plane, and additional steps are taken to resolve the results at the seams between patches. The piecemeal processing can lead to significant overhead. Furthermore, to minimize distortions the number of patches may have to be increased, which can lead to increased complexity of stitching together seams of the different patches.